Subject: loop detection and prevention

From: Choon Lee <[email-masked]>
Date: Fri, 23 Jul 1993 11:11:12 -0700

To continue on the discussions on the topic of loops in DLSw network,
I am suggesting two methods of doing that. One of them involves the
Spanning Tree Protocol, the other does not.

SPANNING TREE
=============

All DLSw nodes that has the Spanning Tree capability (something for the
capabilities exchange siglet as suggested by Scott Adams) can participate 
in the spanning tree protocol.
There are two types of PDUs (Protocol Data Units) that flows in the
protocol: the BPDU (Bridge PDU), and the TCN (Topology Change Notification).

To employ this scheme in DLSw would require the following:
(1) DLSw nodes and its links (both the LAN and the switch side links) are
    required to participate in the Spanning Tree Protocol.
(2) DLSw nodes are to encapsulate/de-encapsulate BPDU and TCN to get them
    across the switch.
(3) The "link cost" of the link between DLSw nodes should be set to a high
    value to make them the "preferred blocked path".

This scheme should be straight forward to implement (for all DLSw nodes that
already support the Spanning Tree Protocol).

I can think of several additions to the DLSw RFC that would be needed:
(1) One new message type to the SSP for handling the BPDU and TCN.
(2) Two new events: link_blocked and link_unblocked that comes from
    the modules that does the spanning tree protocol.
(3) A new state in the DLSw state machine: BLOCKED_STATE.

As Scott has pointed out, developing a non spanning tree solution from
scratch is non trivial. I am suggesting that we use spanning tree despite
some of the inconveniences/inadequacies that may happen, unless someone
has implemented an alternate solution.

NON SPANNING TREE
=================

This protocol must be able to work with parallel DLSw paths at the 
minimum.

      LAN A                         LAN B
	|                             |
	|a ----    b (DLSw)     ---- c|
	|--| A|=================| B|--|
	|  ----                 ----  |
	|                             |
	|  ----                 ----  |
	|--| C|=================| D|--|
	|d ----    e (DLSw)     ---- f|

I am identifying some of the components and types of frames that are
needed:

Loop Detection
--------------

Node A sends out a Loop Detection (LD) frame out its DLSw link (b), and
the LD frame traverses the network along path A-b-B-c-f-D-e-C-d-a-A, and
eventually gets back to A, which detects the presence of a loop, and
takes corrective action. Each DLSw node along the way adds its fingerprint
to the LD frame so that when it gets back to A, the path is recorded in
the LD frame.

Node A will be able to make intelligent decision as which link to put
into blocking state if it has the following information in the LD
frame that it gets back:
(1) Path that the LD frame traverses.
(2) Costs of the DLSw links. 
(3) State of the DLSw links - if link e is already carryiung traffic,
    don't block it even if it is more expensive.
(4) Fingerprint of every DLSw node - to act as tie-breaker in case the
    costs and the states of the links are the same.

For the LD Frame to go around the network as described, it requires the
following:
(1) A multicast address (or functional address for transparent token ring
    frame) for DLSw nodes to receive it from the LAN.
(2) A SAP that gets it into the Loop detection module in the DLSw node.
(3) A new "message type" in the SSP to get it across the switch.

Loop Prevention
---------------
When a loop is detected by node A, and
(1) if node A's DLSw link (b) should go into blocking, node A informs
    node B, and block the link.
(2) if node C's DLSw link (e) should go into blocking, node A informs
    node C, which verifies and confirms, and then blocks the link.

Unblocking blocked link
-----------------------
If node C has its link blocked, when node A detects that its DLSw link
is down, it informs node C so that node C can now unblock its link.

Timer probes
------------
If node C has its link blocked, it periodically sends out a probe to
node A inquiring about its health. Failure to get a positive response
from node A on several consecutive probes causes node C to attempt to 
unblock its link by invoking the loop detection procedure described above.

The scheme above should be extensible to work in various other topologies:
(1) DLSw in parallel with a bridge segment.
(2) 3 or more parallel DLSw.
(3) Two DLSw nodes on one LAN each having a DLSw to the same DLSw node on
    the other LAN.

/choon lee
3Com Corp

----- End Included Message -----